package com.zsjt.dynamicprogramming;

import java.util.Scanner;

/**
 * @author ZhanBo
 * @date 2020/8/1
 */
public class MultipleBackpack {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        /*输入背包的最大重量*/
        int maxWeight = scanner.nextInt();
        /*输入物品的数目*/
        int numbers = scanner.nextInt();
        /*物品重量*/
        int [] weight = new int[numbers];
        /*物品价值*/
        int [] value = new int[numbers];
        /*每个物品的数量*/
        int [] nums = new int[numbers];
    }

    /**
     *  设f[j]表示重量不超过j公斤的最大价值 可得出状态转移方程 ：
     *   f[j]=max{f[j],f[j−k∗w[i]]+k∗v[i]}
     * 多重背包：一维法
     * @param maxWeight 最大重量
     * @param weight 物品重量
     * @param value 物品价值
     * @param nums 物品个数
     * @return
     */
    public static int method(int maxWeight, int[] weight, int[] value, int[] nums) {
        /*第一个值，不算*/
        int n = weight.length - 1;
        int[] f = new int[maxWeight + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = maxWeight; j >= weight[i]; j--) {
                for (int k = 0; k <= nums[i] && j - k * weight[i] >= 0; k++) {
                    f[j] = Math.max(f[j], f[j - k * weight[i]] + k * value[i]);
                }
            }
        }
        /*最优解*/
        return f[maxWeight];
    }
}
